package com.lfg.leetcode.leetcode0;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No47permute {

    public static void main(String[] args) {
        List<List<Integer>> ret = permuteUnique(new int[]{1, 1, 3});
        System.out.println(ret);
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();

        if (nums.length < 1) {
            return ret;
        }
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];

        permute(new ArrayList<Integer>(), nums, ret, visited);
        return ret;
    }

    public static void permute(List<Integer> list, int[] nums, List<List<Integer>> ret, boolean[] visited) {
        int size = nums.length;
        if (size == list.size()) {
            List<Integer> l = new ArrayList<>();
            l.addAll(list);
            ret.add(l);
            return;
        }
        for (int i = 0; i < size; i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && (nums[i] == nums[i - 1]) && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            list.add(nums[i]);
            permute(list, nums, ret, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

